package JianZhiOffer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

/**
 * @author 公众号:程序员的时光
 * @create 2020-09-22 14:50
 * @description
 */
public class No3_PrintList {


   /* //栈实现
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<>();
        Stack<Integer> stack=new Stack<Integer>();
        //入栈
        while(listNode!=null){
            stack.add(listNode.val);
            listNode=listNode.next;
        }
        //取栈顶元素
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }*/
    //递归输出
    public static ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<>();
        if(listNode!=null){
            list=printListFromTailToHead1(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
    //非递归输出
    public static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<>();
        ListNode tmp=listNode;
        while(tmp!=null){
            list.add(0,tmp.val);
            tmp=tmp.next;
        }
        return list;
    }
    /*//reverse逆序输出
    public static void printListFromTailToHead3() {
        ArrayList<Integer> list=new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Collections.reverse(list);
        System.out.println(list);
    }

    //利用ArrayList的插入方法，每次都往index为0的位置插入，那么新插入的元素就会把后插入的元素默认往后移
    public static void printListFromTailToHead4() {
        ArrayList<Integer> list=new ArrayList<>();
        list.add(0,1);
        list.add(0,2);
        list.add(0,3);
        list.add(0,4);
        list.add(0,5);
        System.out.println(list);
    }*/

    public static void main(String[] args) {
        ArrayList list=new ArrayList();
        ListNode head=new ListNode(0,null);
        ListNode PNode=head;

        for(int i=1; i<10; i++){
            ListNode node=new ListNode(i,null);
            PNode.next=node;
            PNode=node;
        }
        //No3_PrintList printList=new No3_PrintList();
        //printList.printListFromTailToHead3();
        //printList.printListFromTailToHead4();
        System.out.println(printListFromTailToHead1(head));
        //System.out.println(printListFromTailToHead1(head));
        System.out.println(printListFromTailToHead2(head));
    }
}


